package demo1;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-24
 * Time: 6:26
 */

class IntCmp implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class TestSort {

    //交换函数swap
    public static void swap(int[] array,int i,int j){
        int tmp =array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    //冒泡排序
    public static void bubbleSort(int[] array){

        for(int i =0;i<array.length-1;++i){
            boolean flg = true;
            for(int j =0;j<array.length-1-i;++j){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = false;
                }
            }
            if(flg){
                break;
            }
        }
    }

    //选择排序
    public static void selectSort(int[] array){
        for(int i =0;i<array.length;++i){
            int minIndex = i;
            for(int j=i+1;j<array.length;++j){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    //插入排序
    public static void insertSort(int[] array){
        for(int i =1;i<array.length;++i){
            int tmp = array[i];
            int j =i-1;
            for(;j>=0;j--){
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    public static void shell(int[] array,int gap){
        for(int i =gap;i<array.length;++i){
            int tmp = array[i];
            int j =i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }


    //希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;
//        while(gap>1){
//            shell(array,gap);
//            gap/=3;
//        }
        shell(array,5);
    }

//    //希尔排序
//    public static void shellSort(int[] array){
//        int gap = array.length;
//        while(gap>1){
//            gap=gap/3+1;
//            for(int i =gap;i<array.length;++i){
//                int tmp = array[i];
//                int j =i-gap;
//                for(;j>=0;j-=gap){
//                    if(array[j]>tmp){
//                        array[j+gap] = array[j];
//                    }else {
//                        break;
//                    }
//                }
//                array[j+gap] = tmp;
//            }
//        }
//    }

    //计数排序
    public static int[] countSort(int[] array){
        //求出数组中最大值和最小值
        int max = array[0];
        int min = array[0];
        for(int i =0;i<array.length;++i){
            if(array[i]>max){
                max = array[i];
            }
            if(array[i]<min){
                min = array[i];
            }
        }
        int[] count = new int[max-min+1];
        int[] tmp = new int[array.length];
        //将数组中的数字都映射到count数组中去
        for(int i =0;i<array.length;++i){
            count[array[i]-min]++;
        }
        //将count数组中的每个下标值都一一显示到tmp数组中
        int index =0;
        for(int i =0;i<count.length;++i){
            while(count[i]>0){
                tmp[index++] = i+min;
                count[i]--;
            }
        }
        return tmp;
    }

    //topK问题-->选择数组中最小的3个元素
    public static int[] topK1(int[] array,int k){
        Heap heap = new Heap();
        //需要建大堆
        int[] tmp = new int[k];
        int i =0;
        for(i=0;i<k;++i){
            tmp[i] = array[i];
        }
        //先将k个元素建成大堆
        heap.createHeap(tmp);
        for(int j =i;j<array.length;++j){
            int ret = heap.peek();
            if(array[j]<ret){
                heap.poll();
                heap.offer(array[j]);
            }
        }
        for(i=0;i<k;++i){
            tmp[i] = heap.peek();
            heap.poll();
        }
        return tmp;
    }
    //topK问题-->选择数组中最大的3个元素
    public static int[] topK(int[] array,int k){
        int[] tmp = new int[k];
        PriorityQueue<Integer> pQ = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int i =0;
        for(int j =0;j<array.length;++j){
            if(pQ.size()<k){
                pQ.offer(array[i]);
                tmp[i] = array[i] ;
            }else {
                int ret = pQ.peek();
                if (array[j] < ret) {
                    pQ.poll();
                    pQ.offer(array[j]);
                }
            }
        }
        for(i=0;i<k;++i){
            tmp[i] = pQ.poll();
        }
        return tmp;
    }

    //非递归法
    public static void partitionNor(int[] array,int left,int right){
          Stack<Integer> stack = new Stack<>();
          int mid = partition3(array,left,right);
          if(left<mid-1){
              stack.push(left);
              stack.push(mid-1);
          }
          if(right>mid+1) {
              stack.push(mid+1);
              stack.push(right);
          }
          while(!stack.isEmpty()){
              right = stack.pop();
              left = stack.pop();
              mid = partition3(array,left,right);
              if(left<mid-1){
                  stack.push(left);
                  stack.push(mid-1);
              }
              if(right>mid+1) {
                  stack.push(mid+1);
                  stack.push(right);
              }
          }
    }

    public static void merge(int[] array,int left,int mid,int right){
         int b1 = left;
         int e1 = mid;
         int b2 = mid+1;
         int e2 = right;
          //合并成一个数组里面
         int[] tmp = new int[right-left+1];
         int k =0;
         while(b1<=e1&&b2<=e2){
             if(array[b1]<array[b2]){
                 tmp[k++] = array[b1++];
             }else {
                 tmp[k++] = array[b2++];
             }
         }
         while(b1<=e1){
             tmp[k++] = array[b1++];
         }
         while(b2<=e2){
             tmp[k++] = array[b2++];
         }
         for(int i =0;i<k;++i){
             array[i+left] = tmp[i];
         }
    }

    public static void mergeSort(int[] array,int left,int right){
        if(left>=right) return;
        int mid = left+((right-left)>>>1);
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,mid,right);
    }

    public static void mergeSortNor(int[] array){
        //归并排序非递归实现
        int gap =1;
        while(gap<array.length){
            for(int i =0;i<array.length;i+=2*gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid>array.length-1){
                    mid = array.length-1;
                }
                int right = mid + gap;
                if(right>array.length-1){
                    right = array.length-1;
                }
                merge(array, left, mid, right);
            }
            gap*=2;
        }
    }

    //挖坑法
    public static int partition1(int[] array,int left,int right){
        int pivot =array[left];
        while(left<right){
            //左边挖坑右边埋坑-->右边找小
            while(left<right&&array[right]>=pivot){
                right--;
            }
            array[left] = array[right];
            //右边挖坑左边埋坑-->左边找大
            while(left<right&&array[left]<=pivot){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }

    //hoare法
    public static int partition2(int[] array,int left,int right){
        int pivot = left;
        while(left<right){
            //右边找小
            while(left<right&&array[right]>=array[pivot]){
                right--;
            }
            //左边找大
            while(left<right&&array[left]<=array[pivot]){
                left++;
            }
            swap(array,left,right);
        }
        //此时两者相遇，更新基准元素位置
        swap(array,left,pivot);
        return left;
    }

    //前后指针法
    public static int partition3(int[] array,int left,int right){
        int pivot = left;
        int prev = left;
        int cur = left+1;
        while(cur<=right){
            //cur主要是找小，然后++prev就是大的元素在交换
            if(array[cur]<array[pivot]&&++prev!=cur){
                swap(array,cur,prev);
            }
            ++cur;
        }
        swap(array,prev,pivot);
        return prev;
    }

    public static int MiddleOfThree(int[] array,int left,int right){
        int mid = left+((right-left)>>>1);
        if(array[left]<array[right]){
            if(array[mid]>array[left]){
                return mid ;
            }else if(array[mid]>array[right]){
                return right;
            }else {
                return left;
            }
        }else {
            //left right
            if(array[mid]>array[left]){
                return left;
            }else if(array[mid]>array[right]){
                return right;
            }else {
                return mid;
            }
        }
    }

    public static void InsertSortToQuick(int[] array,int left,int right){
        for(int i = left;i<=right;++i){
            int tmp = array[i];
            int j = i-1;
            for(;j>=0;j--){
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static void quickSort(int[] array,int left,int right){
        if(left>=right) return ;
        //插入排序优化
        if((left-right+1)<=5){
            InsertSortToQuick(array,left,right);
            return;
        }
        //三数取中优化
        int index = MiddleOfThree(array,left,right);
        swap(array,left,index);
        int mid = partition3(array,left,right);
        quickSort(array,left,mid-1);
        quickSort(array,mid+1,right);
    }

    //for Test

    public static void main(String[] args) {
        int[] array = {10,20,8,25,35,6,18,30,5,15,28};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }


    public static void main6(String[] args) {
        int[] array = {10,20,8,25,35,6,18,30,5,15,28};

        //快速排序
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void main4(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        //快速排序
        partitionNor(array,0,array.length-1);
        //归并排序
        //mergeSort(array,0,array.length-1);
        mergeSortNor(array);
        System.out.println(Arrays.toString(array));
    }

    public static void main2(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37,9,8,1,0,1,4,4,8,2,54,1,2};
        //冒泡排序
        //bubbleSort(array);
        //System.out.println(Arrays.toString(array));
        //选择排序
        //selectSort(array);
        //System.out.println(Arrays.toString(array));
        //插入排序
        //insertSort(array);
        //System.out.println(Arrays.toString(array));
        //希尔排序
        //shellSort(array);
        //System.out.println(Arrays.toString(array));
        //计数排序
        //int[] tmp = countSort(array);
        //System.out.println(Arrays.toString(tmp));
        //topK问题-->选择数组中最大的3个元素
        //System.out.println(Arrays.toString(topK(array,3)));
        //堆排序
        //Heap heap = new Heap();
        //heap.createHeap(array);
        //heap.heapSort(array);
        //System.out.println(Arrays.toString(array));
        //PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    }


//    public static void InsertSortToQuick(int[] array,int left,int right){
//        for(int i = left;i<=right;++i){
//            int tmp = array[i];
//            int j = i-1;
//            for(;j>=0;j--){
//                if(array[j]>tmp){
//                    array[j+1] = array[j];
//                }else {
//                    break;
//                }
//            }
//            array[j+1] = tmp;
//        }
//    }

//
//    public static void quickSort(int[] array,int left,int right){
//        if(left>=right) return ;
//        //插入排序优化
//        if((left-right+1)<=5){
//            InsertSortToQuick(array,left,right);
//            return;
//        }
//        //三数取中
//        int index = medianOfThreeIndex(array,left,right);
//        swap(array,left,index);
//        int mid = partition3(array,left,right);
//        quickSort(array,left,mid-1);
//        quickSort(array,mid+1,right);
//    }
}